/**
 * 链表: 单向链表, 双向链表, 环形链表
 * 问题:
 * > 链表在头部添加元素更加方便, 数组从尾部添加更方便
 * > 特殊处理在链表操作中非常常见,  一个小技巧: 设计一个 dummyHead 虚拟头节点, 让第一个Node并不为null, 代码逻辑可以简化很多
 * > 使用链表实现栈 ( 头部操作都是O(1) )
 * > 实现带有尾指针的链表 -> 实现队列, 双端链表 head tail 维护这两个指针的技巧,  tail添加 head删除 实现队列
 *   特殊的地方: 链表为空的时候, 需要特殊处理的情况  练习: 1. 有dummyHead 实现双端链表  2. 没有dummyHead 实现双端链表
 * > 测试链表性能问题 ?  内存分配的消耗
 *
 * @param <E> 泛型参数
 */
public class LinkedList<E> {

    private class Node {
        public E elem;
        public Node next;

        public Node(E elem, Node next) {
            this.elem = elem;
            this.next = next;
        }

        public Node(E elem) {
            this(elem, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return elem.toString();
        }
    }

    private Node dummyHead;
    public int size;

    public LinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    public void addFirst(E elem) {
        add(0, elem);
    }

    // 实践中, 使用链表时, 通常就不使用索引了
    public void add(int index, E elem) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index must be between 0 and " + size);
        }

        // 统一代码逻辑
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) { // prev -> index - 1 位置, 有虚拟头节点的时候, 则不需要了(小技巧)
            prev = prev.next;
        }

        prev.next = new Node(elem, prev.next);
        size++;
    }

    public void addLast(E elem) {
        add(size, elem);
    }

    // 遍历
    public boolean contains(E elem) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.elem.equals(elem)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 查询
    public E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index must be between 0 and " +(size - 1));

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        return cur.elem;
    }

    public E getFirst() { return get(0); }
    public E getLast() { return get(size-1); }

    // 修改
    public E set(int index, E elem) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index must be between 0 and " +(size - 1));
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        E val = cur.elem; // 保留旧值
        cur.elem = elem;  // 保存新值
        return val;
    }

    // 删除
    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index must be between 0 and " +(size - 1));

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size--;
        return node.elem;
    }

    public E removeFirst() { return remove(0); }
    public E removeLast() { return remove(size-1); }

    public void remove(E elem) {
        if (size == 0) throw new IllegalArgumentException("LinkedList is empty");

        Node pre = dummyHead;
        while (pre.next != null) {
            if (pre.next.elem.equals(elem)) {
                Node delNode = pre.next;
                pre.next = delNode.next;
                delNode.next = null;
                size--;
                return;
            }
            pre = pre.next;
        }
    }
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for (Node cur = dummyHead.next; cur != null; cur = cur.next)
            res.append(cur.elem).append("->");
        res.append("NULL");
        return res.toString();
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}
